#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <time.h>
using namespace std;

#define Max 10000
#define RAND_MAX 100

void RandomGenerate(int a[], int n);
int random_in_range (unsigned int min, unsigned int max);


int random_in_range (unsigned int min, unsigned int max)
{
	//Randomize
	int base_random = rand(); /* in [0, RAND_MAX] */
	if (RAND_MAX == base_random) return random_in_range(min, max);
	/* now guaranteed to be in [0, RAND_MAX) */
	int range       = max - min,
    remainder   = RAND_MAX % range,
    bucket      = RAND_MAX / range;
	/* There are range buckets, plus one smaller interval
     within remainder of RAND_MAX */
	if (base_random < RAND_MAX - remainder) {
		return min + base_random/bucket;
	} else {
		return random_in_range (min, max);
	}
}

void RandomGenerate(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		a[i] = random_in_range(1, 100);
	}
}

void PrintfArray(int a[], int n)
{
	for(int i = 0; i < n; i++)
	{
		printf("  %d", a[i]);
	}
}

int BinarySearch(int a[], int low, int high, int key) {
    if (high < low)
        return -1;
    int middle = (low + high)/2;
    if (key < a[middle])
        return BinarySearch(a, low, middle-1, key);
    else if (key > a[middle])
        return BinarySearch(a, middle+1, high, key);
    else if (key == a[middle])
        return middle;
}

int main()
{
	int a[Max], N[100];
	for(int i = 1; i < 20; i++)
	{
		N[i] = 1000*i;
	}
	for(int i = 1; i < 11; i++)
	{
		int key = a[i] = random_in_range(1, 100);
		int n = N[i];
		printf("============N=%d=============\n\n", n);
		RandomGenerate(a,n);
		sort(a,a+n);
		//PrintfArray(a,n);

		clock_t start = clock();
		printf("\nFound %d at position %d\n", key, BinarySearch(a,0,n-1,key));
		printf("     Time elapsed: %f\n\n", ((double)clock() - start) / CLOCKS_PER_SEC);

		getch();
	}
}